package Array.BinarySearch;

import java.util.Arrays;
import java.util.PriorityQueue;

public class 寻找第K大的元素 {

    public static int findKth(int[] a, int n, int K) {
        // write code here快速排序的思路
        //第k大，一次快排的数的位置即应该在的位置，如果排号的位置等于 k-1则为结果
        return findK(a, 0, n-1, K);

    }

    private static int quickSort(int[] a, int start, int end){

        int privot = a[start];
        int i = start;
        int j = end;
        while(i<j){
            //快排，从后往前找到第一个比目标值大的
            while(i<j && a[j]<privot){
                j--;
            }
            if(i<j){
                a[i++] = a[j];
            }
            while(i<j && a[i]>privot){
                i++;
            }
            if(i<j){
                a[j--] = a[i];
            }
        }
        //一次排序结束,i的位置是排好的位置
        a[i] = privot;
        return i;


    }

    private static  int findK(int[] a, int start, int end, int K){
        if(start<=end){
            int priot = quickSort(a, start,end);
            if(priot > K-1){
                return findK(a,start,priot-1,K);
            }else if(priot < K-1){
                return findK(a,priot+1, end,K);
            }else{
                return a[priot];
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, 1, 3, 1, 2, 4, 5, 6, 9, 8};
        int[] ints = Arrays.stream(nums).distinct().toArray();
        System.out.println(findKth(nums, nums.length, 8));
        System.out.println(heap(ints, ints.length, 8));
    }


    /**
     * 堆解决
     * */
    private static int heap(int[] a, int n, int K){
        PriorityQueue<Integer> pq = new PriorityQueue<>(); //小顶堆
        for (int i = 0; i < a.length; i++) {
            pq.add(a[i]);
            if(pq.size()>K){
                pq.poll();
            }
        }
        return pq.peek();
    }
}
